home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 17 / CU Amiga Magazine's Super CD-ROM 17 (1997)(EMAP Images)(GB)[!][issue 1997-12].iso / CUCD / Programming / Make / source / dir.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-27  |  25.0 KB  |  1,033 lines
  1. /* Directory hashing for GNU Make.
  2. Copyright (C) 1988,89,91,92,93,94,95,96,97 Free Software Foundation, Inc.
  3. This file is part of GNU Make.
  4.  
  5. GNU Make is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.
  9.  
  10. GNU Make is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with GNU Make; see the file COPYING.  If not, write to
  17. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18.  
  19. #include "make.h"
  20.  
  21. #ifdef    HAVE_DIRENT_H
  22. # include <dirent.h>
  23. # define NAMLEN(dirent) strlen((dirent)->d_name)
  24. #else
  25. # define dirent direct
  26. # define NAMLEN(dirent) (dirent)->d_namlen
  27. # ifdef HAVE_SYS_NDIR_H
  28. #  include <sys/ndir.h>
  29. # endif
  30. # ifdef HAVE_SYS_DIR_H
  31. #  include <sys/dir.h>
  32. # endif
  33. # ifdef HAVE_NDIR_H
  34. #  include <ndir.h>
  35. # endif
  36. # ifdef HAVE_VMSDIR_H
  37. #  include "vmsdir.h"
  38. # endif /* HAVE_VMSDIR_H */
  39. #endif
  40.  
  41. /* In GNU systems, <dirent.h> defines this macro for us.  */
  42. #ifdef _D_NAMLEN
  43. #undef NAMLEN
  44. #define NAMLEN(d) _D_NAMLEN(d)
  45. #endif
  46.  
  47. #if (defined (POSIX) || defined (WINDOWS32)) && !defined (__GNU_LIBRARY__)
  48. /* Posix does not require that the d_ino field be present, and some
  49.    systems do not provide it. */
  50. #define REAL_DIR_ENTRY(dp) 1
  51. #define FAKE_DIR_ENTRY(dp)
  52. #else
  53. #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  54. #define FAKE_DIR_ENTRY(dp) (dp->d_ino = 1)
  55. #endif /* POSIX */
  56.  
  57. #ifdef __MSDOS__
  58. #include <ctype.h>
  59. #include <fcntl.h>
  60.  
  61. /* If it's MSDOS that doesn't have _USE_LFN, disable LFN support.  */
  62. #ifndef _USE_LFN
  63. #define _USE_LFN 0
  64. #endif
  65.  
  66. static char *
  67. dosify (filename)
  68.      char *filename;
  69. {
  70.   static char dos_filename[14];
  71.   char *df;
  72.   int i;
  73.  
  74.   if (filename == 0 || _USE_LFN)
  75.     return filename;
  76.  
  77.   /* FIXME: what about filenames which violate
  78.      8+3 constraints, like "config.h.in", or ".emacs"?  */
  79.   if (strpbrk (filename, "\"*+,;<=>?[\\]|") != 0)
  80.     return filename;
  81.  
  82.   df = dos_filename;
  83.  
  84.   /* First, transform the name part.  */
  85.   for (i = 0; *filename != '\0' && i < 8 && *filename != '.'; ++i)
  86.     *df++ = tolower (*filename++);
  87.  
  88.   /* Now skip to the next dot.  */
  89.   while (*filename != '\0' && *filename != '.')
  90.     ++filename;
  91.   if (*filename != '\0')
  92.     {
  93.       *df++ = *filename++;
  94.       for (i = 0; *filename != '\0' && i < 3 && *filename != '.'; ++i)
  95.     *df++ = tolower (*filename++);
  96.     }
  97.  
  98.   /* Look for more dots.  */
  99.   while (*filename != '\0' && *filename != '.')
  100.     ++filename;
  101.   if (*filename == '.')
  102.     return filename;
  103.   *df = 0;
  104.   return dos_filename;
  105. }
  106. #endif /* __MSDOS__ */
  107.  
  108. #ifdef WINDOWS32
  109. #include "pathstuff.h"
  110. #endif
  111.  
  112. #ifdef _AMIGA
  113. #include <ctype.h>
  114.  
  115. static char *
  116. amigafy (filename)
  117.      char *filename;
  118. {
  119.   static char amiga_filename[136];
  120.   char *df;
  121.   int i;
  122.  
  123.   if (filename == 0)
  124.     return 0;
  125.  
  126.   df = amiga_filename;
  127.  
  128.   /* First, transform the name part.  */
  129.   for (i = 0; *filename != '\0'; ++i)
  130.   {
  131.     *df++ = tolower (*filename);
  132.     ++filename;
  133.   }
  134.  
  135.   *df = 0;
  136.  
  137.   return amiga_filename;
  138. }
  139. #endif /* _AMIGA */
  140.  
  141. #ifdef VMS
  142.  
  143. static int
  144. vms_hash (name)
  145.     char *name;
  146. {
  147.   int h = 0;
  148.   int g;
  149.  
  150.   while (*name)
  151.     {
  152.       h = (h << 4) + *name++;
  153.       g = h & 0xf0000000;
  154.       if (g)
  155.     {
  156.       h = h ^ (g >> 24);
  157.       h = h ^ g;
  158.     }
  159.     }
  160.   return h;
  161. }
  162.  
  163. /* fake stat entry for a directory */
  164. static int
  165. vmsstat_dir (name, st)
  166.     char *name;
  167.     struct stat *st;
  168. {
  169.   char *s;
  170.   int h;
  171.   DIR *dir;
  172.  
  173.   dir = opendir (name);
  174.   if (dir == 0)
  175.     return -1;
  176.   closedir (dir);
  177.   s = strchr (name, ':');    /* find device */
  178.   if (s)
  179.     {
  180.       *s++ = 0;
  181.       st->st_dev = (char *)vms_hash (name);
  182.       h = vms_hash (s);
  183.       *(s-1) = ':';
  184.     }
  185.   else
  186.     {
  187.       st->st_dev = 0;
  188.       s = name;
  189.       h = vms_hash (s);
  190.     }
  191.  
  192.   st->st_ino[0] = h & 0xff;
  193.   st->st_ino[1] = h & 0xff00;
  194.   st->st_ino[2] = h >> 16;
  195.  
  196.   return 0;
  197. }
  198. #endif /* VMS */
  199.  
  200. /* Hash table of directories.  */
  201.  
  202. #ifndef    DIRECTORY_BUCKETS
  203. #define DIRECTORY_BUCKETS 199
  204. #endif
  205.  
  206. struct directory_contents
  207.   {
  208.     struct directory_contents *next;
  209.  
  210.     dev_t dev;            /* Device and inode numbers of this dir.  */
  211. #ifdef WINDOWS32
  212.     /*
  213.      * Inode means nothing on WINDOWS32. Even file key information is
  214.      * unreliable because it is random per file open and undefined
  215.      * for remote filesystems. The most unique attribute I can
  216.      * come up with is the fully qualified name of the directory. Beware
  217.      * though, this is also unreliable. I'm open to suggestion on a better
  218.      * way to emulate inode.
  219.      */
  220.     char *path_key;
  221.     int   mtime;        /* controls check for stale directory cache */
  222.     int   fs_flags;     /* FS_FAT, FS_NTFS, ... */
  223. #define FS_FAT      0x1
  224. #define FS_NTFS     0x2
  225. #define FS_UNKNOWN  0x4
  226. #else
  227. #ifdef VMS
  228.     ino_t ino[3];
  229. #else
  230.     ino_t ino;
  231. #endif
  232. #endif /* WINDOWS32 */
  233.     struct dirfile **files;    /* Files in this directory.  */
  234.     DIR *dirstream;        /* Stream reading this directory.  */
  235.   };
  236.  
  237. /* Table of directory contents hashed by device and inode number.  */
  238. static struct directory_contents *directories_contents[DIRECTORY_BUCKETS];
  239.  
  240. struct directory
  241.   {
  242.     struct directory *next;
  243.  
  244.     char *name;            /* Name of the directory.  */
  245.  
  246.     /* The directory's contents.  This data may be shared by several
  247.        entries in the hash table, which refer to the same directory
  248.        (identified uniquely by `dev' and `ino') under different names.  */
  249.     struct directory_contents *contents;
  250.   };
  251.  
  252. /* Table of directories hashed by name.  */
  253. static struct directory *directories[DIRECTORY_BUCKETS];
  254.  
  255.  
  256. /* Never have more than this many directories open at once.  */
  257.  
  258. #define MAX_OPEN_DIRECTORIES 10
  259.  
  260. static unsigned int open_directories = 0;
  261.  
  262.  
  263. /* Hash table of files in each directory.  */
  264.  
  265. struct dirfile
  266.   {
  267.     struct dirfile *next;
  268.     char *name;            /* Name of the file.  */
  269.     char impossible;        /* This file is impossible.  */
  270.   };
  271.  
  272. #ifndef    DIRFILE_BUCKETS
  273. #define DIRFILE_BUCKETS 107
  274. #endif
  275.  
  276. static int dir_contents_file_exists_p PARAMS ((struct directory_contents *dir, char *filename));
  277. static struct directory *find_directory PARAMS ((char *name));
  278.  
  279. /* Find the directory named NAME and return its `struct directory'.  */
  280.  
  281. static struct directory *
  282. find_directory (name)
  283.      register char *name;
  284. {
  285.   register unsigned int hash = 0;
  286.   register char *p;
  287.   register struct directory *dir;
  288. #ifdef WINDOWS32
  289.   char* w32_path;
  290.   char  fs_label[BUFSIZ];
  291.   char  fs_type[BUFSIZ];
  292.   long  fs_serno;
  293.   long  fs_flags;
  294.   long  fs_len;
  295. #endif
  296. #ifdef VMS
  297.   if ((*name == '.') && (*(name+1) == 0))
  298.     name = "[]";
  299.   else
  300.     name = vmsify (name,1);
  301. #endif
  302.  
  303.   for (p = name; *p != '\0'; ++p)
  304.     HASHI (hash, *p);
  305.   hash %= DIRECTORY_BUCKETS;
  306.  
  307.   for (dir = directories[hash]; dir != 0; dir = dir->next)
  308.     if (strieq (dir->name, name))
  309.       break;
  310.  
  311.   if (dir == 0)
  312.     {
  313.       struct stat st;
  314.  
  315.       /* The directory was not found.  Create a new entry for it.  */
  316.  
  317.       dir = (struct directory *) xmalloc (sizeof (struct directory));
  318.       dir->next = directories[hash];
  319.       directories[hash] = dir;
  320.       dir->name = savestring (name, p - name);
  321.  
  322.       /* The directory is not in the name hash table.
  323.      Find its device and inode numbers, and look it up by them.  */
  324.  
  325. #ifdef VMS
  326.       if (vmsstat_dir (name, &st) < 0)
  327. #else
  328.       if (stat (name, &st) < 0)
  329. #endif
  330.     {
  331.     /* Couldn't stat the directory.  Mark this by
  332.        setting the `contents' member to a nil pointer.  */
  333.       dir->contents = 0;
  334.     }
  335.       else
  336.     {
  337.       /* Search the contents hash table; device and inode are the key.  */
  338.  
  339.       struct directory_contents *dc;
  340.  
  341. #ifdef WINDOWS32
  342.           w32_path = w32ify(name, 1);
  343.           hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ctime;
  344. #else
  345. #ifdef VMS
  346.     hash = ((unsigned int) st.st_dev << 16)
  347.         | ((unsigned int) st.st_ino[0]
  348.         + (unsigned int) st.st_ino[1]
  349.         + (unsigned int) st.st_ino[2]);
  350. #else
  351.       hash = ((unsigned int) st.st_dev << 16) | (unsigned int) st.st_ino;
  352. #endif
  353. #endif
  354.       hash %= DIRECTORY_BUCKETS;
  355.  
  356.       for (dc = directories_contents[hash]; dc != 0; dc = dc->next)
  357. #ifdef WINDOWS32
  358.             if (!strcmp(dc->path_key, w32_path))
  359. #else
  360.         if (dc->dev == st.st_dev
  361. #ifdef VMS
  362.         && dc->ino[0] == st.st_ino[0]
  363.         && dc->ino[1] == st.st_ino[1]
  364.         && dc->ino[2] == st.st_ino[2])
  365. #else
  366.          && dc->ino == st.st_ino)
  367. #endif
  368. #endif /* WINDOWS32 */
  369.           break;
  370.  
  371.       if (dc == 0)
  372.         {
  373.           /* Nope; this really is a directory we haven't seen before.  */
  374.  
  375.           dc = (struct directory_contents *)
  376.         xmalloc (sizeof (struct directory_contents));
  377.  
  378.           /* Enter it in the contents hash table.  */
  379.           dc->dev = st.st_dev;
  380. #ifdef WINDOWS32
  381.               dc->path_key = strdup(w32_path);
  382.               dc->mtime = st.st_mtime;
  383.  
  384.               /*
  385.                * NTFS is the only WINDOWS32 filesystem that bumps mtime
  386.                * on a directory when files are added/deleted from
  387.                * a directory.
  388.                */
  389.               w32_path[3] = '\0';
  390.               if (GetVolumeInformation(w32_path,
  391.                      fs_label, sizeof (fs_label),
  392.                      &fs_serno, &fs_len,
  393.                      &fs_flags, fs_type, sizeof (fs_type)) == FALSE)
  394.                 dc->fs_flags = FS_UNKNOWN;
  395.               else if (!strcmp(fs_type, "FAT"))
  396.                 dc->fs_flags = FS_FAT;
  397.               else if (!strcmp(fs_type, "NTFS"))
  398.                 dc->fs_flags = FS_NTFS;
  399.               else
  400.                 dc->fs_flags = FS_UNKNOWN;
  401. #else
  402. #ifdef VMS
  403.           dc->ino[0] = st.st_ino[0];
  404.           dc->ino[1] = st.st_ino[1];
  405.           dc->ino[2] = st.st_ino[2];
  406. #else
  407.           dc->ino = st.st_ino;
  408. #endif
  409. #endif /* WINDOWS32 */
  410.           dc->next = directories_contents[hash];
  411.           directories_contents[hash] = dc;
  412.  
  413.           dc->dirstream = opendir (name);
  414.           if (dc->dirstream == 0)
  415.         {
  416.         /* Couldn't open the directory.  Mark this by
  417.            setting the `files' member to a nil pointer.  */
  418.           dc->files = 0;
  419.         }
  420.           else
  421.         {
  422.           /* Allocate an array of buckets for files and zero it.  */
  423.           dc->files = (struct dirfile **)
  424.             xmalloc (sizeof (struct dirfile *) * DIRFILE_BUCKETS);
  425.           bzero ((char *) dc->files,
  426.              sizeof (struct dirfile *) * DIRFILE_BUCKETS);
  427.  
  428.           /* Keep track of how many directories are open.  */
  429.           ++open_directories;
  430.           if (open_directories == MAX_OPEN_DIRECTORIES)
  431.             /* We have too many directories open already.
  432.                Read the entire directory and then close it.  */
  433.             (void) dir_contents_file_exists_p (dc, (char *) 0);
  434.         }
  435.         }
  436.  
  437.       /* Point the name-hashed entry for DIR at its contents data.  */
  438.       dir->contents = dc;
  439.     }
  440.     }
  441.  
  442.   return dir;
  443. }
  444.  
  445. /* Return 1 if the name FILENAME is entered in DIR's hash table.
  446.    FILENAME must contain no slashes.  */
  447.  
  448. static int
  449. dir_contents_file_exists_p (dir, filename)
  450.      register struct directory_contents *dir;
  451.      register char *filename;
  452. {
  453.   register unsigned int hash;
  454.   register char *p;
  455.   register struct dirfile *df;
  456.   register struct dirent *d;
  457. #ifdef WINDOWS32
  458.   struct stat st;
  459.   int rehash = 0;
  460. #endif
  461.  
  462.   if (dir == 0 || dir->files == 0)
  463.     {
  464.     /* The directory could not be stat'd or opened.  */
  465.       return 0;
  466.     }
  467. #ifdef __MSDOS__
  468.   filename = dosify (filename);
  469. #endif
  470.  
  471. #ifdef _AMIGA
  472.   filename = amigafy (filename);
  473. #endif
  474.  
  475. #ifdef VMS
  476.   filename = vmsify (filename,0);
  477. #endif
  478.  
  479.   hash = 0;
  480.   if (filename != 0)
  481.     {
  482.       if (*filename == '\0')
  483.     {
  484.     /* Checking if the directory exists.  */
  485.       return 1;
  486.     }
  487.  
  488.       for (p = filename; *p != '\0'; ++p)
  489.     HASH (hash, *p);
  490.       hash %= DIRFILE_BUCKETS;
  491.  
  492.       /* Search the list of hashed files.  */
  493.  
  494.       for (df = dir->files[hash]; df != 0; df = df->next)
  495.     {
  496.       if (strieq (df->name, filename))
  497.         {
  498.           return !df->impossible;
  499.         }
  500.     }
  501.     }
  502.  
  503.   /* The file was not found in the hashed list.
  504.      Try to read the directory further.  */
  505.  
  506.   if (dir->dirstream == 0)
  507.     {
  508. #ifdef WINDOWS32
  509.       /*
  510.        * Check to see if directory has changed since last read. FAT
  511.        * filesystems force a rehash always as mtime does not change
  512.        * on directories (ugh!).
  513.        */
  514.       if (dir->path_key &&
  515.           (dir->fs_flags & FS_FAT ||
  516.            (stat(dir->path_key, &st) == 0 &&
  517.             st.st_mtime > dir->mtime))) {
  518.  
  519.         /* reset date stamp to show most recent re-process */
  520.         dir->mtime = st.st_mtime;
  521.  
  522.         /* make sure directory can still be opened */
  523.         dir->dirstream = opendir(dir->path_key);
  524.  
  525.         if (dir->dirstream)
  526.           rehash = 1;
  527.         else
  528.           return 0; /* couldn't re-read - fail */
  529.       } else
  530. #endif
  531.     /* The directory has been all read in.  */
  532.       return 0;
  533.     }
  534.  
  535.   while ((d = readdir (dir->dirstream)) != 0)
  536.     {
  537.       /* Enter the file in the hash table.  */
  538.       register unsigned int newhash = 0;
  539.       unsigned int len;
  540.       register unsigned int i;
  541.  
  542.       if (!REAL_DIR_ENTRY (d))
  543.     continue;
  544.  
  545.       len = NAMLEN (d);
  546.       for (i = 0; i < len; ++i)
  547.     HASHI (newhash, d->d_name[i]);
  548.       newhash %= DIRFILE_BUCKETS;
  549. #ifdef WINDOWS32
  550.       /*
  551.        * If re-reading a directory, check that this file isn't already
  552.        * in the cache.
  553.        */
  554.       if (rehash) {
  555.         for (df = dir->files[newhash]; df != 0; df = df->next)
  556.           if (streq(df->name, d->d_name))
  557.             break;
  558.       } else
  559.         df = 0;
  560.  
  561.       /*
  562.        * If re-reading a directory, don't cache files that have
  563.        * already been discovered.
  564.        */
  565.       if (!df) {
  566. #endif
  567.  
  568.       df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
  569.       df->next = dir->files[newhash];
  570.       dir->files[newhash] = df;
  571.       df->name = savestring (d->d_name, len);
  572.       df->impossible = 0;
  573. #ifdef WINDOWS32
  574.       }
  575. #endif
  576.       /* Check if the name matches the one we're searching for.  */
  577.       if (filename != 0
  578.       && newhash == hash && strieq (d->d_name, filename))
  579.     {
  580.       return 1;
  581.     }
  582.     }
  583.  
  584.   /* If the directory has been completely read in,
  585.      close the stream and reset the pointer to nil.  */
  586.   if (d == 0)
  587.     {
  588.       --open_directories;
  589.       closedir (dir->dirstream);
  590.       dir->dirstream = 0;
  591.     }
  592.   return 0;
  593. }
  594.  
  595. /* Return 1 if the name FILENAME in directory DIRNAME
  596.    is entered in the dir hash table.
  597.    FILENAME must contain no slashes.  */
  598.  
  599. int
  600. dir_file_exists_p (dirname, filename)
  601.      register char *dirname;
  602.      register char *filename;
  603. {
  604.   return dir_contents_file_exists_p (find_directory (dirname)->contents,
  605.                      filename);
  606. }
  607.  
  608. /* Return 1 if the file named NAME exists.  */
  609.  
  610. int
  611. file_exists_p (name)
  612.      register char *name;
  613. {
  614.   char *dirend;
  615.   char *dirname;
  616.  
  617. #ifndef    NO_ARCHIVES
  618.   if (ar_name (name))
  619.     return ar_member_date (name) != (time_t) -1;
  620. #endif
  621.  
  622. #ifdef VMS
  623.   dirend = rindex (name, ']');
  624.   dirend++;
  625.   if (dirend == (char *)1)
  626.     return dir_file_exists_p ("[]", name);
  627. #else /* !VMS */
  628.   dirend = rindex (name, '/');
  629. #if defined (WINDOWS32) || defined (__MSDOS__)
  630.   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
  631.   {
  632.     char *bslash = rindex(name, '\\');
  633.     if (!dirend || bslash > dirend)
  634.       dirend = bslash;
  635.     /* The case of "d:file" is unhandled.  But I don't think
  636.        such names can happen here.  */
  637.   }
  638. #endif /* WINDOWS32 || __MSDOS__ */
  639.   if (dirend == 0)
  640. #ifndef _AMIGA
  641.     return dir_file_exists_p (".", name);
  642. #else /* !VMS && !AMIGA */
  643.     return dir_file_exists_p ("", name);
  644. #endif /* AMIGA */
  645. #endif /* VMS */
  646.  
  647.   if (dirend == name)
  648.     dirname = "/";
  649.   else
  650.     {
  651.       dirname = (char *) alloca (dirend - name + 1);
  652.       bcopy (name, dirname, dirend - name);
  653.       dirname[dirend - name] = '\0';
  654.     }
  655.   return dir_file_exists_p (dirname, dirend + 1);
  656. }
  657.  
  658. /* Mark FILENAME as `impossible' for `file_impossible_p'.
  659.    This means an attempt has been made to search for FILENAME
  660.    as an intermediate file, and it has failed.  */
  661.  
  662. void
  663. file_impossible (filename)
  664.      register char *filename;
  665. {
  666.   char *dirend;
  667.   register char *p = filename;
  668.   register unsigned int hash;
  669.   register struct directory *dir;
  670.   register struct dirfile *new;
  671.  
  672. #ifdef VMS
  673.   dirend = rindex (p, ']');
  674.   dirend++;
  675.   if (dirend == (char *)1)
  676.     dir = find_directory ("[]");
  677. #else
  678.   dirend = rindex (p, '/');
  679. #if defined (WINDOWS32) || defined (__MSDOS__)
  680.   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
  681.   {
  682.     char *bslash = rindex(p, '\\');
  683.     if (!dirend || bslash > dirend)
  684.       dirend = bslash;
  685.     /* The case of "d:file" is unhandled.  But I don't think
  686.        such names can happen here.  */
  687.   }
  688. #endif /* WINDOWS32 or __MSDOS__ */
  689.   if (dirend == 0)
  690. #ifdef _AMIGA
  691.     dir = find_directory ("");
  692. #else /* !VMS && !AMIGA */
  693.     dir = find_directory (".");
  694. #endif /* AMIGA */
  695. #endif /* VMS */
  696.   else
  697.     {
  698.       char *dirname;
  699.       if (dirend == p)
  700.     dirname = "/";
  701.       else
  702.     {
  703.       dirname = (char *) alloca (dirend - p + 1);
  704.       bcopy (p, dirname, dirend - p);
  705.       dirname[dirend - p] = '\0';
  706.     }
  707.       dir = find_directory (dirname);
  708.       filename = p = dirend + 1;
  709.     }
  710.  
  711.   for (hash = 0; *p != '\0'; ++p)
  712.     HASHI (hash, *p);
  713.   hash %= DIRFILE_BUCKETS;
  714.  
  715.   if (dir->contents == 0)
  716.     {
  717.       /* The directory could not be stat'd.  We allocate a contents
  718.      structure for it, but leave it out of the contents hash table.  */
  719.       dir->contents = (struct directory_contents *)
  720.     xmalloc (sizeof (struct directory_contents));
  721. #ifdef WINDOWS32
  722.       dir->contents->path_key = NULL;
  723.       dir->contents->mtime = 0;
  724. #else  /* WINDOWS32 */
  725. #ifdef VMS
  726.       dir->contents->dev = 0;
  727.       dir->contents->ino[0] = dir->contents->ino[1] =
  728.     dir->contents->ino[2] = 0;
  729. #else
  730.       dir->contents->dev = dir->contents->ino = 0;
  731. #endif
  732. #endif /* WINDOWS32 */
  733.       dir->contents->files = 0;
  734.       dir->contents->dirstream = 0;
  735.     }
  736.  
  737.   if (dir->contents->files == 0)
  738.     {
  739.       /* The directory was not opened; we must allocate the hash buckets.  */
  740.       dir->contents->files = (struct dirfile **)
  741.     xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
  742.       bzero ((char *) dir->contents->files,
  743.          sizeof (struct dirfile) * DIRFILE_BUCKETS);
  744.     }
  745.  
  746.   /* Make a new entry and put it in the table.  */
  747.  
  748.   new = (struct dirfile *) xmalloc (sizeof (struct dirfile));
  749.   new->next = dir->contents->files[hash];
  750.   dir->contents->files[hash] = new;
  751.   new->name = savestring (filename, strlen (filename));
  752.   new->impossible = 1;
  753. }
  754.  
  755. /* Return nonzero if FILENAME has been marked impossible.  */
  756.  
  757. int
  758. file_impossible_p (filename)
  759.      char *filename;
  760. {
  761.   char *dirend;
  762.   register char *p = filename;
  763.   register unsigned int hash;
  764.   register struct directory_contents *dir;
  765.   register struct dirfile *next;
  766.  
  767. #ifdef VMS
  768.   dirend = rindex (filename, ']');
  769.   if (dirend == 0)
  770.     dir = find_directory ("[]")->contents;
  771. #else
  772.   dirend = rindex (filename, '/');
  773. #if defined (WINDOWS32) || defined (__MSDOS__)
  774.   /* Forward and backslashes might be mixed.  We need the rightmost one.  */
  775.   {
  776.     char *bslash = rindex(filename, '\\');
  777.     if (!dirend || bslash > dirend)
  778.       dirend = bslash;
  779.     /* The case of "d:file" is unhandled.  But I don't think
  780.        such names can happen here.  */
  781.   }
  782. #endif /* WINDOWS32 || __MSDOS__ */
  783.   if (dirend == 0)
  784. #ifdef _AMIGA
  785.     dir = find_directory ("")->contents;
  786. #else /* !VMS && !AMIGA */
  787.     dir = find_directory (".")->contents;
  788. #endif /* AMIGA */
  789. #endif /* VMS */
  790.   else
  791.     {
  792.       char *dirname;
  793.       if (dirend == filename)
  794.     dirname = "/";
  795.       else
  796.     {
  797.       dirname = (char *) alloca (dirend - filename + 1);
  798.       bcopy (p, dirname, dirend - p);
  799.       dirname[dirend - p] = '\0';
  800.     }
  801.       dir = find_directory (dirname)->contents;
  802.       p = filename = dirend + 1;
  803.     }
  804.  
  805.   if (dir == 0 || dir->files == 0)
  806.     /* There are no files entered for this directory.  */
  807.     return 0;
  808.  
  809. #ifdef __MSDOS__
  810.   p = filename = dosify (p);
  811. #endif
  812. #ifdef _AMIGA
  813.   p = filename = amigafy (p);
  814. #endif
  815. #ifdef VMS
  816.   p = filename = vmsify (p, 1);
  817. #endif
  818.  
  819.   for (hash = 0; *p != '\0'; ++p)
  820.     HASH (hash, *p);
  821.   hash %= DIRFILE_BUCKETS;
  822.  
  823.   for (next = dir->files[hash]; next != 0; next = next->next)
  824.     if (strieq (filename, next->name))
  825.       return next->impossible;
  826.  
  827.   return 0;
  828. }
  829.  
  830. /* Return the already allocated name in the
  831.    directory hash table that matches DIR.  */
  832.  
  833. char *
  834. dir_name (dir)
  835.      char *dir;
  836. {
  837.   return find_directory (dir)->name;
  838. }
  839.  
  840. /* Print the data base of directories.  */
  841.  
  842. void
  843. print_dir_data_base ()
  844. {
  845.   register unsigned int i, dirs, files, impossible;
  846.   register struct directory *dir;
  847.  
  848.   puts ("\n# Directories\n");
  849.  
  850.   dirs = files = impossible = 0;
  851.   for (i = 0; i < DIRECTORY_BUCKETS; ++i)
  852.     for (dir = directories[i]; dir != 0; dir = dir->next)
  853.       {
  854.     ++dirs;
  855.     if (dir->contents == 0)
  856.       printf ("# %s: could not be stat'd.\n", dir->name);
  857.     else if (dir->contents->files == 0)
  858. #ifdef WINDOWS32
  859.           printf ("# %s (key %s, mtime %d): could not be opened.\n",
  860.                   dir->name, dir->contents->path_key,dir->contents->mtime);
  861. #else  /* WINDOWS32 */
  862. #ifdef VMS
  863.       printf ("# %s (device %d, inode [%d,%d,%d]): could not be opened.\n",
  864.           dir->name, dir->contents->dev,
  865.           dir->contents->ino[0], dir->contents->ino[1],
  866.           dir->contents->ino[2]);
  867. #else
  868.       printf ("# %s (device %ld, inode %ld): could not be opened.\n",
  869.           dir->name, (long int) dir->contents->dev,
  870.           (long int) dir->contents->ino);
  871. #endif
  872. #endif /* WINDOWS32 */
  873.     else
  874.       {
  875.         register unsigned int f = 0, im = 0;
  876.         register unsigned int j;
  877.         register struct dirfile *df;
  878.         for (j = 0; j < DIRFILE_BUCKETS; ++j)
  879.           for (df = dir->contents->files[j]; df != 0; df = df->next)
  880.         if (df->impossible)
  881.           ++im;
  882.         else
  883.           ++f;
  884. #ifdef WINDOWS32
  885.             printf ("# %s (key %s, mtime %d): ",
  886.                     dir->name, dir->contents->path_key, dir->contents->mtime);
  887. #else  /* WINDOWS32 */
  888. #ifdef VMS
  889.         printf ("# %s (device %d, inode [%d,%d,%d]): ",
  890.             dir->name, dir->contents->dev,
  891.             dir->contents->ino[0], dir->contents->ino[1],
  892.             dir->contents->ino[2]);
  893. #else
  894.         printf ("# %s (device %d, inode %d): ",
  895.             dir->name, dir->contents->dev, dir->contents->ino);
  896. #endif
  897. #endif /* WINDOWS32 */
  898.         if (f == 0)
  899.           fputs ("No", stdout);
  900.         else
  901.           printf ("%u", f);
  902.         fputs (" files, ", stdout);
  903.         if (im == 0)
  904.           fputs ("no", stdout);
  905.         else
  906.           printf ("%u", im);
  907.         fputs (" impossibilities", stdout);
  908.         if (dir->contents->dirstream == 0)
  909.           puts (".");
  910.         else
  911.           puts (" so far.");
  912.         files += f;
  913.         impossible += im;
  914.       }
  915.       }
  916.  
  917.   fputs ("\n# ", stdout);
  918.   if (files == 0)
  919.     fputs ("No", stdout);
  920.   else
  921.     printf ("%u", files);
  922.   fputs (" files, ", stdout);
  923.   if (impossible == 0)
  924.     fputs ("no", stdout);
  925.   else
  926.     printf ("%u", impossible);
  927.   printf (" impossibilities in %u directories.\n", dirs);
  928. }
  929.  
  930. /* Hooks for globbing.  */
  931.  
  932. #include <glob.h>
  933.  
  934. /* Structure describing state of iterating through a directory hash table.  */
  935.  
  936. struct dirstream
  937.   {
  938.     struct directory_contents *contents; /* The directory being read.  */
  939.  
  940.     unsigned int bucket;    /* Current hash bucket.  */
  941.     struct dirfile *elt;    /* Current elt in bucket.  */
  942.   };
  943.  
  944. /* Forward declarations.  */
  945. static __ptr_t open_dirstream PARAMS ((const char *));
  946. static struct dirent *read_dirstream PARAMS ((__ptr_t));
  947.  
  948. static __ptr_t
  949. open_dirstream (directory)
  950.      const char *directory;
  951. {
  952.   struct dirstream *new;
  953.   struct directory *dir = find_directory ((char *)directory);
  954.  
  955.   if (dir->contents == 0 || dir->contents->files == 0)
  956.     /* DIR->contents is nil if the directory could not be stat'd.
  957.        DIR->contents->files is nil if it could not be opened.  */
  958.     return 0;
  959.  
  960.   /* Read all the contents of the directory now.  There is no benefit
  961.      in being lazy, since glob will want to see every file anyway.  */
  962.  
  963.   (void) dir_contents_file_exists_p (dir->contents, (char *) 0);
  964.  
  965.   new = (struct dirstream *) xmalloc (sizeof (struct dirstream));
  966.   new->contents = dir->contents;
  967.   new->bucket = 0;
  968.   new->elt = new->contents->files[0];
  969.  
  970.   return (__ptr_t) new;
  971. }
  972.  
  973. static struct dirent *
  974. read_dirstream (stream)
  975.      __ptr_t stream;
  976. {
  977.   struct dirstream *const ds = (struct dirstream *) stream;
  978.   register struct dirfile *df;
  979.   static char *buf;
  980.   static unsigned int bufsz;
  981.  
  982.   while (ds->bucket < DIRFILE_BUCKETS)
  983.     {
  984.       while ((df = ds->elt) != 0)
  985.     {
  986.       ds->elt = df->next;
  987.       if (!df->impossible)
  988.         {
  989.           /* The glob interface wants a `struct dirent',
  990.          so mock one up.  */
  991.           struct dirent *d;
  992.           unsigned int len = strlen (df->name) + 1;
  993.           if (sizeof *d - sizeof d->d_name + len > bufsz)
  994.         {
  995.           if (buf != 0)
  996.             free (buf);
  997.           bufsz *= 2;
  998.           if (sizeof *d - sizeof d->d_name + len > bufsz)
  999.             bufsz = sizeof *d - sizeof d->d_name + len;
  1000.           buf = xmalloc (bufsz);
  1001.         }
  1002.           d = (struct dirent *) buf;
  1003.           FAKE_DIR_ENTRY (d);
  1004. #ifdef _DIRENT_HAVE_D_NAMLEN
  1005.           d->d_namlen = len - 1;
  1006. #endif
  1007.           memcpy (d->d_name, df->name, len);
  1008.           return d;
  1009.         }
  1010.     }
  1011.       if (++ds->bucket == DIRFILE_BUCKETS)
  1012.     break;
  1013.       ds->elt = ds->contents->files[ds->bucket];
  1014.     }
  1015.  
  1016.   return 0;
  1017. }
  1018.  
  1019. void
  1020. dir_setup_glob (gl)
  1021.      glob_t *gl;
  1022. {
  1023.   extern int stat ();
  1024.  
  1025.   /* Bogus sunos4 compiler complains (!) about & before functions.  */
  1026.   gl->gl_opendir = open_dirstream;
  1027.   gl->gl_readdir = read_dirstream;
  1028.   gl->gl_closedir = free;
  1029.   gl->gl_stat = stat;
  1030.   /* We don't bother setting gl_lstat, since glob never calls it.
  1031.      The slot is only there for compatibility with 4.4 BSD.  */
  1032. }
  1033.